package com.base.binarytree;

import jdk.nashorn.internal.runtime.regexp.joni.exception.ValueException;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName: BuildTree
 * @Description: 105. 从前序与中序遍历序列构造二叉树
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 * @author: li
 * @Date: 2021/8/26 7:58 下午
 */
public class BuildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        if (preLen != inLen) {
            // 长度不同，可能是数据错误
            throw new ValueException("长度不同，可能是数据错误");
        }
        // 将值和序号存至哈希表中（优化查找中序遍历中的根结点的位置）
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inLen; i++) {
            map.put(inorder[i], i);
        }

        return buildTree(preorder, 0, preLen - 1, map, 0, inLen - 1);

    }

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> map, int inStart, int inEnd) {
        // 终止条件，当数组的索引越界时
        if (preStart > preEnd) {
            return null;
        }
        // 前序遍历根结点
        TreeNode root = new TreeNode(preorder[preStart]);
        // 中序遍历根结点的位置
        int mid = map.get(preorder[preStart]);
        root.left = buildTree(preorder, preStart + 1, mid + preStart - inStart, map, inStart, mid - 1);
        root.right = buildTree(preorder, mid + preStart - inStart + 1, preEnd, map, mid + 1, inEnd);
        return root;
    }
}
